package leetcode.D400.T316;

import java.util.*;

class Solution {
//    public String removeDuplicateLetters(String s) {
//        StringBuilder sb = new StringBuilder();
//        Deque<Character> dq = new LinkedList<>();
//        int[] count = new int[256];
//        boolean[] hash = new boolean[256];
//        for(int i=0; i<s.length(); ++i) {
//            count[s.charAt(i)]++;
//        }
//        for(int i=0; i<s.length(); ++i) {
//            char c = s.charAt(i);
//            count[c]--;
//            if(hash[c] == true) continue;
//            while(!dq.isEmpty() && dq.getLast() > c) {
//                if(count[dq.getLast()] == 0) {
//                    break;
//                }
//                hash[dq.removeLast()] = false;
//            }
//            dq.addLast(c);
//            hash[c] = true;
//        }
//        while(!dq.isEmpty()) {
//            sb.append(dq.removeLast());
//        }
//        return sb.reverse().toString();
//    }

    // 二刷
    /*public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        boolean[] has = new boolean[26];
        Deque<Character> dq = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<s.length(); ++i) {
            count[s.charAt(i)-'a']++;
        }
        for(int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            count[c-'a']--;
            if(has[c-'a']) {
                continue;
            }
            while(!dq.isEmpty() && dq.getFirst() > c) {
                if(count[dq.getFirst()-'a'] == 0) {
                    break;
                }
                has[dq.removeFirst()-'a'] = false;
            }
            dq.addFirst(c);
            has[c-'a'] = true;
        }
        while(!dq.isEmpty()) {
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }*/

    // 三刷
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26];
        Map<Character, Integer> map = new HashMap<>();
        Set<Character> set = new HashSet<>();
        Deque<Character> dq = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<s.length(); ++i) {
            count[s.charAt(i)-'a']++;
        }
        for(int i=0; i<s.length(); ++i) {
            char c = s.charAt(i);
            count[c-'a']--;
            if (set.contains(c)) {
                continue;
            }
            while(!dq.isEmpty() && dq.getLast() > c && count[dq.getLast()-'a'] > 0) {
                set.remove(dq.removeLast());
            }
            dq.addLast(c);
            set.add(c);
        }
        while(!dq.isEmpty()) {
            sb.append(dq.removeFirst());
        }
        return sb.toString();
    }
}
